package com.github.hgkmail.hello.leetcode101.design;

import java.util.*;

//插入、删除O(1) -> HashMap
//随机访问O(1) -> ArrayList
//RandomizedSet = HashMap + ArrayList（ArrayList只在尾部进行插入和删除）
//todo 怎么用 HashSet 处理冲突，代替链表？
public class LC381InsertDeleteGetRandomO1DuplicatesAllowed {
    public static class RandomizedCollection {
        //value使用list，存储重复元素的位置
        private Map<Integer, List<Integer>> index;
        private List<Integer> list;
        private Random random;

        public RandomizedCollection() {
            //(value, array index list)
            index = new HashMap<>();
            //只在尾部进行插入和删除
            list = new ArrayList<>();

            random = new Random();
        }

        public boolean insert(int val) {
            boolean exist = index.containsKey(val);

            int len=list.size();
            list.add(val); // append到列表尾部
            if (exist) {
                index.get(val).add(len);
            } else {
                List<Integer> duplicates = new LinkedList<>();
                duplicates.add(len);
                index.put(val, duplicates);
            }

            return !exist;
        }

        public boolean remove(int val) {
            if (!index.containsKey(val)) {
                return false;
            }
            List<Integer> duplicates = index.get(val);
            //有多个
            if (duplicates.size()>1) {
                delAtLoc(duplicates.get(0), val);
                return true;
            }
            //只有一个
            int loc = duplicates.get(0);
            delAtLoc(loc, val);

            return true;
        }

        public int getRandom() {
            int loc = random.nextInt(list.size()); //[0,size)
            return list.get(loc);
        }

        private void delAtLoc(int loc, int val) {
            int lastLoc = list.size()-1;
            int lastNum = list.get(lastLoc);
            index.get(lastNum).remove(new Integer(lastLoc));
            //用last的元素代替loc的元素
            list.set(loc, lastNum);
            index.get(lastNum).add(loc);
            //删除ArrayList最后一个元素，不用移动数组，符合O(1)
            list.remove(lastLoc);
            if (index.get(val).size()>1) {
                index.get(val).remove(new Integer(loc));
            } else {
                index.remove(val);
            }
        }
    }

    public static void main(String[] args) {
        RandomizedCollection randomizedCollection = new RandomizedCollection();
        randomizedCollection.insert(0);
        randomizedCollection.insert(1);
        randomizedCollection.remove(0);
        randomizedCollection.insert(2);
        randomizedCollection.remove(1);
        System.out.println(randomizedCollection.getRandom());
    }
}
